package 力扣_高阶数据结构.优先级队列;

import java.util.*;

/**
 * @author zx
 * @create 2022-08-15 20:43
 */
public class 前K个高频元素_347 {
    /**
     * @return 最小堆
     */
    public int[] topKFrequent(int[] nums, int k) {
        int[] res = new int[k];
        Map<Integer,Integer> map = new HashMap<>();
        for(int i = 0;i < nums.length;i++){
            map.put(nums[i],map.getOrDefault(nums[i],0) + 1);
        }
        PriorityQueue<int[]> queue = new PriorityQueue<>(new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[1] - o2[1];
            }
        });
        //因为这里key,value都是int型,所以queue可以存储数组
        for(Map.Entry<Integer,Integer> entry : map.entrySet()){
            int key = entry.getKey();
            int value = entry.getValue();
            if(queue.size() < k){
                queue.offer(new int[]{key,value});
            }else{
                int[] peek = queue.peek();
                if(peek[1] > value){
                    continue;
                }else{
                    queue.poll();
                    queue.offer(new int[]{key,value});
                }
            }
        }
        for(int i = 0;i < k;i++){
            res[i] = queue.poll()[0];
        }
        return res;
    }

    /**
     * @return 对map中的value排序
     */
    public int[] topKFrequent2(int[] nums, int k) {
        int[] res = new int[k];
        LinkedHashMap<Integer,Integer> map = new LinkedHashMap<>();
        for(int i = 0;i < nums.length;i++){
            map.put(nums[i],map.getOrDefault(nums[i],0) + 1);
        }
        List<Map.Entry<Integer,Integer>> entries = new ArrayList<>(map.entrySet());
        Collections.sort(entries, new Comparator<Map.Entry<Integer, Integer>>() {
            @Override
            public int compare(Map.Entry<Integer, Integer> o1, Map.Entry<Integer, Integer> o2) {
                //频率逆序排序
                return o2.getValue() - o1.getValue();
            }
        });
        int i = 0;
        for(Map.Entry<Integer,Integer> entry : entries){
            if(i < k){
                res[i++] = entry.getKey();
            }
        }
        return res;
    }

    /**
     * @return 哈希 + 最小堆 + 自己构建类
     */
    public int[] topKFrequent3(int[] nums, int k) {
        Map<Integer,Integer> map = new HashMap<>();
        for(int i = 0;i < nums.length;i++){
            if(map.containsKey(nums[i])){
                map.put(nums[i],map.get(nums[i]) + 1);
            }else{
                map.put(nums[i],1);
            }
        }
        PriorityQueue<Freq> queue = new PriorityQueue<>(new Comparator<Freq>() {
            @Override
            public int compare(Freq o1, Freq o2) {
                return o1.count - o2.count;
            }
        });
        for(Map.Entry<Integer,Integer> entry : map.entrySet()){
            if(queue.size() < k){
                queue.offer(new Freq(entry.getKey(), entry.getValue()));
            }else{
                Freq freq = queue.peek();
                if(entry.getValue() < freq.count){
                    continue;
                }else{
                    queue.poll();
                    queue.offer(new Freq(entry.getKey(),entry.getValue()));
                }
            }
        }
        int[] res = new int[k];
        for(int i = 0;i < k;i++){
            res[i] = queue.poll().key;
        }
        return res;
    }
    private class Freq{
        private int key;
        private int count;
        //每个不重复的元素以及其出现的次数
        public Freq(int key, int count) {
            this.key = key;
            this.count = count;
        }
    }
}
